package com.peng.leetcode.search;

/**
 * Main12
 *
 * @author: lupeng6
 * @create: 2023/3/9 15:30
 */
public class Main12 {
    /**
     * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
     *
     * 每行的元素从左到右升序排列。
     * 每列的元素从上到下升序排列。
     *
     * class Solution {
     *     public boolean searchMatrix(int[][] matrix, int target) {
     *
     *     }
     * }
     *
     * @author lupeng6
     * @date 2023/3/9 15:31
     */
    public static void main(String[] args) {

    }

    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            int[] arr = matrix[i];
            if (arr[0] <= target && arr[arr.length - 1] >= target) {
                int l = 0;
                int r = arr.length - 1;
                while (l < r) {
                    int mid = l + (r - l) / 2;
                    if (arr[mid] == target) {
                        return true;
                    }
                    if (arr[mid] < target) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
            }
        }
        return false;
    }

}
